package offerbook;

/**
 * 把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。
 * 输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。
 * 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。
 * NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。
 * @date 2020/3/7 23:39
 */
public class Code08_FindMinInRotateArr {
    //1:arr严格递增
    public static int minNumberInRotateArray1(int [] nums) {
        if(nums == null || nums.length == 0) return 0;
        if(nums.length == 1) return nums[0];
        int l = 0; // l始终从左侧往 最小值靠近，但是始终属于左侧大的区域
        int r = nums.length -1; // r始终从右侧往 最小值靠近，但是始终属于右侧小的区域
        int mid = (l + r)/2;
        if (nums[r] > nums[0]) { // sorted
            return nums[0];
        }
        while (true){
            //最终r必定会来到min，l会在min前一个位置
            if(r - l == 1){
                return nums[r];
            }
            if(nums[mid] >= nums[l]){
                //注意这里不能+1，否则l可能超过左侧大的区域
                l = mid;
            }else if(nums[mid] <= nums[nums.length-1]){
                //同理r不能 -1
                r = mid;
            }
            mid = (l + r)/2;
        }
    }
    //2:arr非递减
    public static int minNumberInRotateArray2(int [] array) {
        if(array == null || array.length == 0) return 0;
        int l = 0; // l始终从左侧往 最小值靠近，但是始终属于左侧大的区域
        int r = array.length -1; // r始终从右侧往 最小值靠近，但是始终属于右侧小的区域
        int mid = (l + r)/2;
        while (true){
            //最终r必定会来到min，l会在min前一个位置
            if(r - l == 1){
                return array[r];
            }
            if(array[l] == array[r] && array[l] == array[mid]){
                return inOrder(array,l,r);
            }
            if(array[mid] >= array[l]){
                //注意这里不能+1，否则l可能超过左侧大的区域
                l = mid;
            }else if(array[mid] <= array[array.length-1]){
                //同理r不能 -1
                r = mid;
            }
            mid = (l + r)/2;
        }
    }

    private static int inOrder(int[] array, int l, int r) {
        int min = array[l];
        for (int e : array) min = Math.min(min,e);
        return min;
    }

    public static void main(String[] args) {
        int[]arr = {6501,6828,6963,7036,7422,7674,8146,8468,8704,8717,9170,9359,9719,9895,9896,9913,9962,154,293,334,492,1323,1479,1539,1727,1870,1943,2383,2392,2996,3282,3812,3903,4465,4605,4665,4772,4828,5142,5437,5448,5668,5706,5725,6300,6335};
        System.out.println(minNumberInRotateArray2(arr));
    }
}
